<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>2209. 用地毯覆盖后的最少白色砖块</title>
</head>
<body>
    <script>
//         给你一个下标从 0 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。

// floor[i] = '0' 表示地板上第 i 块砖块的颜色是 黑色 。
// floor[i] = '1' 表示地板上第 i 块砖块的颜色是 白色 。
// 同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条 黑色 的地毯，每一条 黑色 的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色 砖块的数目 最小 。地毯相互之间可以覆盖。

// 请你返回没被覆盖的白色砖块的 最少 数目。

 

// 示例 1：



// 输入：floor = "10110101", numCarpets = 2, carpetLen = 2
// 输出：2
// 解释：
// 上图展示了剩余 2 块白色砖块的方案。
// 没有其他方案可以使未被覆盖的白色砖块少于 2 块。
// 示例 2：



// 输入：floor = "11111", numCarpets = 2, carpetLen = 3
// 输出：0
// 解释：
// 上图展示了所有白色砖块都被覆盖的一种方案。
// 注意，地毯相互之间可以覆盖。
 

// 提示：

// 1 <= carpetLen <= floor.length <= 1000
// floor[i] 要么是 '0' ，要么是 '1' 。
// 1 <= numCarpets <= 1000

/**
 * @param {string} floor
 * @param {number} numCarpets
 * @param {number} carpetLen
 * @return {number}
 */
//  var minimumWhiteTiles = function(floor, numCarpets, carpetLen) {
//   if (numCarpets * carpetLen >= floor.length) {
//     return 0;
//   }
//   let n = 0;
//   let zeroStr = '';
//   for (let i = 0; i < carpetLen; i++) {
//     zeroStr += '0';
//   }
//   while(numCarpets) {// 还有地毯
//     if (!floor.match(/1/g)) { // 全部是黑色
//       return 0;
//     }
//     for (let i = 0; i < floor.length - carpetLen; i++) {
//       const str = floor.slice(i, i + carpetLen);
//       const zeros = str.match(/1/g);
//       console.log(zeros, 'zeros', carpetLen - n);
      
//       if (zeros && zeros.length === carpetLen - n) { // 找到一个区间白块为地毯的长度减去轮回遍历的次数
//         floor = floor.slice(0, i) + zeroStr + floor.slice(i + carpetLen); // 截取掉这个区间
//         console.log(i, i + carpetLen);
        
//         console.log(floor);
        
//         numCarpets--; // 地毯减一
//         if (numCarpets === 0) { // 地毯用完了
//           console.log('here');
          
//           let num = floor.match(/1/g)
//           return num.length || 0;
//         }
//         continue
//       }
//     }
//     n++; // 回环次数加一
//   }
    
// };

// console.log(minimumWhiteTiles("0001100111110001111111110111010110100111000111111001011011010000011011101100001011111111111111111011110101111011010101001011111111111111111011110101000101010010101111111011011111111101100111111101101111000011101101001110011011100010100111111111111111101011001111101110101110111001111111111110110111111101011110111000111011011010111011111111111111111011111011011111111110001110001100111001101101011111111111111111101011011111101101100111111111111111", 8, 16));


// let str = '0001100111110001111111110111010110100111000111111001011011010000011011101100001000000000000000001011110101111011010101001000000000000000001011110101000101010010101111111011011111111101100111111101101111000011101101001110011011100010100111111111111111101011001111101110101110111001111111111110110111111101011110111000111011011010111011111111111111111011111011011111111110001110001100111001101101011111111111111111101011011111101101100111111111111111'
// console.log(str.match(/1/g).length);
// let n = '0001100111110001111111110111010110100111000111111001011011010000011011101100001011111111111111111011110101111011010101001011111111111111111011110101000101010010101111111011011111111101100111111101101111000011101101001110011011100010100111111111111111101011001111101110101110111001111111111110110111111101011110111000111011011010111011111111111111111011111011011111111110001110001100111001101101011111111111111111101011011111101101100111111111111111';
// console.log(n.match(/1/g).length);
// console.log(n.slice(80, 96));
// console.log(n.slice(122, 138));
// console.log(n.slice(235, 251));
// console.log(n.slice(322, 338));
// console.log(n.slice(395, 411));
// console.log(n.slice(162, 178));
// console.log(n.slice(274, 290));
// console.log(n.slice(350, 366));

const INF = 0x3f3f3f3f; // 定义一个无穷大的常量，用于初始化数组。

var minimumWhiteTiles = function(floor, numCarpets, carpetLen) {
    let n = floor.length; // 地板的长度。
    let d = new Array(n + 1).fill(INF); // d数组用于存储不使用地毯时，前i个瓷砖中未被覆盖的白色瓷砖数量。
    let f = new Array(n + 1).fill(INF); // f数组用于存储使用j条地毯时，前i个瓷砖中未被覆盖的白色瓷砖数量。
    d[0] = 0; // 初始状态，没有瓷砖时，未被覆盖的白色瓷砖数量为0。

    // 预处理d数组，计算不使用地毯时，每个位置的前缀和。
    for (let i = 1; i <= n; i++) {
        d[i] = d[i - 1] + (floor[i - 1] === '1' ? 1 : 0); // 如果当前瓷砖是白色的，则累加到前缀和。
    }

    // 动态规划主循环，计算使用j条地毯时的最小未覆盖白色瓷砖数量。
    for (let j = 1; j <= numCarpets; j++) {
        f[0] = 0; // 初始状态，没有瓷砖时，未被覆盖的白色瓷砖数量为0。
        for (let i = 1; i <= n; i++) {
            // 不使用地毯覆盖当前瓷砖的情况。
            f[i] = f[i - 1] + (floor[i - 1] === '1' ? 1 : 0);
            // 使用地毯覆盖当前瓷砖的情况，取不覆盖和覆盖中的最小值。
            f[i] = Math.min(f[i], d[Math.max(0, i - carpetLen)]);
        }
        // 交换d和f数组，为下一轮迭代做准备。
        [d, f] = [f, d];
    }

    // 返回使用numCarpets条地毯后，所有瓷砖中未被覆盖的白色瓷砖数量。
    return d[n];
};




    </script>
</body>
</html>